package com.zhaopin.theswordreferstooffer;


import java.util.Objects;
import java.util.Stack;

/**
 * @author yin.peide
 * @date 2021-06-01 17:22
 * 面试题5： 从尾到头打印链表
 * <p>
 * 思路 ： 1、用栈实现
 * 2、用一个双链表，新的链表使用头插法
 * 3、使用递归
 */
public class Offer5 {

    public static void main(String[] args) {
        LinkOffer linkOffer1 = new LinkOffer(1);
        LinkOffer linkOffer2 = new LinkOffer(2);
        LinkOffer linkOffer3 = new LinkOffer(3);
        LinkOffer linkOffer4 = new LinkOffer(4);
        linkOffer3.setNext(linkOffer4);
        linkOffer2.setNext(linkOffer3);
        linkOffer1.setNext(linkOffer2);
        //1 -> 2-> 3 -> 4
        //正常遍历
        getNextLinkObject(linkOffer1);
//        getFromTailToHead(linkOffer1);
//        recursion(linkOffer1);
        getNextLinkObject(theSecondLink(linkOffer1));
    }

    //正常头到尾部的遍历
    public static void getNextLinkObject(LinkOffer linkOffer) {
        System.out.println(linkOffer.getValue());
        if (Objects.nonNull(linkOffer.getNext())) {
            LinkOffer linkTemp = linkOffer.getNext();
            getNextLinkObject(linkTemp);
        } else {

            System.out.println("结束了");
        }
    }


    //使用栈 从尾部到头部遍历
    public static void getFromTailToHead(LinkOffer linkOffer) {

        Stack<LinkOffer> stack = new Stack<>();
        //入栈
        while (linkOffer != null) {
            stack.push(linkOffer);
            linkOffer = linkOffer.getNext();
        }
        //出栈
        while (!stack.empty()) {
            LinkOffer linkOffer1 = stack.pop();
            System.out.println(linkOffer1.getValue());
        }

    }


    /**
     * 使用递归 进行尾部到到头部的遍历
     */
    public static void recursion(LinkOffer linkOffer) {
        if (linkOffer.getNext() != null) {
            recursion(linkOffer.getNext());
        }
        System.out.println(linkOffer.getValue());
    }


    /**
     * 使用第二个链表 双链表搞 头插法
     */
    public static LinkOffer theSecondLink(LinkOffer head) {

        LinkOffer newHead = null;
        while (head != null) {
            //先保存访问的节点的下一个节点，保存起来
            //留着下一步访问的
            LinkOffer temp = head.getNext();
            //每次访问的原链表节点都会成为新链表的头结点，
            //其实就是把新链表挂到访问的原链表节点的
            //后面就行了
            head.setNext(newHead);
            //更新新链表
            newHead = head;
            //重新赋值，继续访问
            head = temp;
        }
        //返回新链表
        return newHead;


    }

}


class LinkOffer {
    private int value;
    private LinkOffer next;

    public LinkOffer getNext() {
        return next;
    }

    public void setNext(LinkOffer next) {
        this.next = next;
    }

    public LinkOffer(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}
